/* PROBLEME N° 7
 * Trouver le 10001eme nombre premier
 *
 * Date de résolution : 15 Jan 2010 O1:O1
 * Temps d'exécution : 0m0.036sec
 * Réponse : 104743
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int premier(int);

int main(int argc, char *argv[])
{
    int nbNbPremiers = 1; // On connaît déjà déjà un nombre premier 2
    int candidat = 1;
    
    do
    {
        candidat += 2;
        if(premier(candidat))
        {
            printf("%d\n", candidat);
            nbNbPremiers += 1;
        }
    } while(nbNbPremiers != 10001);

    return 0;
}

/*
 * 1 n'est pas un nombre premier
 * Tout nombre premier différent de 2 est impair
 * Tout nombre premier supérieur à 3 peut être écrit sous 
 * la forme 6k +/- 1
 * Si pour un nombre n, il n'existe pas de diviseurs inférieurs
 * ou égaux à sqrt(n), alors n est premier
 */
int premier(int n)
{
    int i = 0, limite = 0;

    if(n == 1)
        return 0;
    else if(n < 4) // 2 et 3 sont des nombres premiers
        return 1;
    else if(n % 2 == 0)
        return 0;
    else if(n < 9) // 4, 6, et 8 ont été exclus par la condition précédente
        return 1;
    else if(n % 3 == 0)
        return 0;
    else
    {
        limite = (int)sqrt(n);
        i = 5;
        while(i <= limite)
        {
            if(n % i == 0)
                return 0;
            if(n % (i + 2) == 0)
                return 0;
            i += 6;
        }
        return 1;
    }
}
